//
//  Problem120.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/26.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 120. 三角形最小路径和
 给定一个三角形 triangle ，找出自顶向下的最小路径和。

 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 示例 1：

 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 输出：11
 解释：如下面简图所示：
    2
   3 4
  6 5 7
 4 1 8 3
 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 示例 2：

 输入：triangle = [[-10]]
 输出：-10
  

 提示：

 1 <= triangle.length <= 200
 triangle[0].length == 1
 triangle[i].length == triangle[i - 1].length + 1
 -104 <= triangle[i][j] <= 104

 */
@objcMembers class Problem120: NSObject {
    func solution() {
        print(minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]]))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[m][n]
     2: dp[i][j]到达最最后一行的最小和
     3: dp[i][j] = dp[i][j] + min(dp[i+1][j], dp[i+1][j+1])
     */
    func minimumTotal(_ triangle: [[Int]]) -> Int {
        if triangle.count == 1 {
            return triangle[0][0]
        }
        
        var dp:[[Int]] = []
        for i in 0..<triangle.count {
            dp.append(Array(repeating: 105, count: triangle[i].count))
        }
        return getMinTotal(triangle, &dp, 0, 0)
    }
    
    func getMinTotal(_ triangle:[[Int]], _ dp: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i == triangle.count - 1  {       // 结束条件：最后一行
            dp[i][j] = triangle[i][j]
            return dp[i][j]
        }
        
        if dp[i][j] != 105 {
            return dp[i][j]
        }
        
        dp[i][j] = triangle[i][j] + min(getMinTotal(triangle, &dp, i+1, j), getMinTotal(triangle, &dp, i+1, j+1))
        return dp[i][j]
    }
}
